정렬 알고리즘

리스트의 값을 오름차순, 내림차순으로 재배치하는 알고리즘

Stable VS Unstable

중복된 키가 존재하는 정렬 했을 때, 기존 리스트에 있던 순서대로 정렬이 되는 것.

unsorted_list = [3, 6, 2₁, 7, 2₂]
sorted_list = [2₁, 2₂, 3, 6, 7]

Stable Algorithms

• 선택정렬
• 버블 정렬
• 합병 정렬

Unstable Algorithm

• 힙정렬
• 선택정렬
• 퀵정렬

In-place vs Out-of-place

In-place sorting은 추가적인 메모리를 거의 또는 전혀 사용하지 않고 주어진 데이터 구조 내에서 요소들을 정렬하는 방식을 말한다.

In-place sorting은 다음과 같은 특징이 있다.

1. 메모리 효율성: 추가적인 메모리를 거의 사용하지 않기 때문에 메모리 사용량이 적다.
2. 원본 데이터 수정: 정렬 과정에서 원본 배열이나 리스트가 수정된다.
3. 제한된 공간에서의 정렬: 메모리가 제한적인 환경에서 유용하다.

대표 적인 예시

• 버블정렬
• 삽입정렬
• 퀵정렬

정렬 알고리즘 종류

버블 정렬(Bubble Sort)

매번 연속된 두개의 값을 비교해서 정렬하는 방법. 거품이 수면으로 올라오는 듯 하여 붙여진 정렬방

구현방법

1. 배열의 i번째 인덱스와 i+1번째 인덱스의 키를 비교한다.
2. i번째 인덱스의 키가 더 크다면 자리를 상호 교환(swap)한다.
3. 위 과정을 반복수행한다.

시간 복잡도

• 각 루프마다 비교대상이 하나씩 줄어든어서

  (N-1) + (N-2) + (N-3) + …. + 1 이 되고 결국 N * (N-1) /2 가 되어서

  O(N^2) 의 시간 복잡도를 가진다.

특징

장점

• 구현이 간단하다.
• 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.

단점

• 데이터를 전부 비교해야 하므로 시간 효율이 좋지 않다.

구현

def bubble_sort(arr):
		for i in range(n-1, 0, -1):
			for j in range(i):
				if arr[j] > arr[j+1]:
					arr[j], arr[j+1] = arr[j+1], arr[j]

선택 정렬(Selection Sort)

배열에서 작은 제일 작은 값을 골라서 앞으로 보내는 정렬 방법

구현 방법

1. 정렬되지 않은 배열에서 가장 작은 값을 찾는다.
2. 가장 작은 값을 맨 앞으로 보낸다.
3. 정렬되지 않은 배열이 +1
4. 반복

시간복잡도

• 이중 루프사용해서 시간복잡도 : O(N^2)

특징

장점

• 구현이 간단하다.
• 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.
• 비교 횟수에 비해 교환 횟수가 적다.

단점

• 시간이 오래 걸린다.
• 정렬된 상태에서 데이터가 추가되었을 때 정렬 효율이 좋지 않다.

코드

def selection_sort(arr):
        for i in range(len(arr)):
            min_index = i
            for j in range(i+1, len(arr)):
                if arr[min_index] > arr[j]:
                    min_index = j
            arr[i], arr[min_index] = arr[min_index], arr[i]
        return arr

삽입 정렬(Insertion Sort)

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해서 자신의 위치를 찾아서 삽입하는 정렬

구현방법

1. 2번째 값부터 for 문
2. 앞의 값들과 비교해서 작으면 비교 인덱스 -1, 크면 그 자리에 삽입
3. 반복

시간 복잡도

• 입력자료가 정렬되어 있는 경우 n-1 번의 루프가 실행되고 1번의 비교가 이루어져기 때문에 시간복잡도 : O(N)
• 입력 자료가 역순으로 정렬되어 있는 경우 n-1 번의 루프에서 n-1 번의 비교 발생해서 시간 복잡도 : O(N^2)
• 평균 복잡도 : O(N^2)

특징

장점

• 입력 데이터가 정렬되어 있을 경우 속도가 빠르다.
• 이미 정렬된 값은 교환이 일어나지 않는다.

단점

• 입력 데이터가 역순으로 정렬되어 있을 수록 성능이 현저히 떨어진다.
• 삽입을 구현해야 하므로 자료구조에 영향을 많이 받는다.
• 루프가 거듭될수록 정렬 범위가 넓어진다.

구현

def insertion_sort(arr):
    for i in range(1, len(array)):
			    for j in range(i, 0, -1): 
			        if array[j] < array[j-1]:
			            array[j], array[j-1] = array[j-1], array[j]
			        else:
			            break

힙정렬

최대 힙, 최소 힙으로 정렬

계수 정렬(Counting Sort)

말 그대로 갯수를 세서 정렬하는 알고리즘

계수정렬의 조건

1. 데이터(값)은 양수여야 한다.
2. 값의 범위가 너무 크지 않아야 한다.(메모리 사이즈 이하)

구현 방법

1. 모든 범위의 수가 담길 수 있는 리스트 생성
2. 루프문 돌면서 값의 개수 세기
3. 인데스를 인덱스 값만큼 출

시간 복잡도

• 배열을 순회하면서 갯수 셀 때 O(N) , 카운트 배열을 순회할 때 O(N) 이므로 전체적으로 O(N) 을 가진다.

특징

장점

• 매우 빠른 시간 복잡도

단점

• 데이터 범위 만큼의 리스트를 만들어야해서 메모리 낭비

구현

def counting_sort(arr):
    max_arr = max(arr)
    count = [0] * (max_arr + 1)
    sorted_arr = list()
    
    for i in arr:	# 카운팅
        count[i] += 1

    for i in range(max_arr + 1):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

정렬 알고리즘 시간 복잡도 비교

references

• https://hsp1116.tistory.com/33
• https://hyo-ue4study.tistory.com/68